데이터베이스 연구회지(SIGDB)
Current Result Document :
| 한글제목(Korean Title) |
그래프 분할 기반 RETE 네트워크 분산 처리 |
| 영문제목(English Title) |
Distributed Processing of a RETE Network based on Graph Partitioning |
| 저자(Author) |
최형주
윤수식
이재길
Hyeongju Choi
Susik Yoon
Jae-Gil Lee
|
| 원문수록처(Citation) |
VOL 33 NO. 02 PP. 0113 ~ 0126 (2017. 08) |
한글내용
(Korean Abstract) |
RETE 네트워크는 생성 규칙 엔진 (production rule engine)의 주요 구성요소로서, 입력되는 데이터 스트림에서 정의된 규칙을 빠르게 탐지한 후 대응되는 행동을 수행하는 복합 이벤트 처리 (complex event processing)를 위해 널리 사용되고 있다. 최근 사물인터넷의 발전, 소셜 미디어 및 모바일 기기의 대중화로 인해 스트림 데이터에 대한 복합 이벤트 처리의 수요가 증가하고 있으며, 특히 입력 스트림의 양과 속도가 증가함에 따라 클라우드 환경에서의 분산 처리의 필요성 또한 함께 대두되고 있다. RETE 네트워크를 분산 처리하고자한 기존의 연구에서는 다양한 계산량을 가지는 규칙들을 효율적으로 분배하지 못했고, 분산 처리에 사용된 서버간의 네트워크 전송량 또한 고려하지 못했다. 본 논문에서는 이와 같은 문제를 해결하기 위해 그래프 분할 기법을 이용하여 RETE 네트워크를 분산 처리하는 방법을 제안한다. Bisection spectral graph partitioning을 재귀적으로 적용하여 각 서버에 계산량을 효율적으로 분배하고, 서버간 네트워크 사용량 또한 최소화하였다. 세 종류의 실제 데이터를 사용하여 기존 연구 대비 본 방법이 처리시간, 불균형 정도, 네트워크 사용량 관점에서 우수함을 확인하였다.
|
영문내용
(English Abstract) |
A RETE network is the main component of a production rule engine, which is mainly used for complex event processing to detect predefined rules against data stream and perform a corresponding action. Recently, the demand for complex event processing of stream data has increased due to advancements in Internet of Things, social media, and smartphone applications. At the same time, with growing size and input rate of stream data, the needs for a distributed processing is also increasing. The previous research on a distributed processing of a RETE network did not show efficient resource distribution and did not consider the cost of network usage. To deal with these problems, we proposed a distributed processing of a RETE network based on graph partitioning. More specifically, by recursively applying a bisection spectral graph partitioning algorithm on a RETE network, we distributed fair resources into each server and minimized the overall network usage. Performance experiments using three types of real data sets results better performances in terms of runtimes, degree of imbalance, and total network usage compared to the alternative algorithms.
|
| 키워드(Keyword) |
RETE 네트워크
복합 이벤트 처리
분산 복합 이벤트 처리
RETE Network
Complex Event Processing
Distributed Complex Event Processing
|
| 파일첨부 |
PDF 다운로드
|
